package subject_set.offer100;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2022/10/25 22:04
 **/
public class Offer59 {
    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            Deque<Integer> q = new LinkedList<>();
            int[] res = new int[nums.length-k+1];
            for(int i = 1-k, j = 0; j < nums.length; ++i, ++j){
                // 删除头一个元素
                if(i > 0 && q.peekFirst() == nums[i-1]) q.removeFirst();
                // 维持一个递增序列
                while(!q.isEmpty() && q.peekLast() < nums[j]) q.removeLast();
                q.offer(nums[j]);
                if(i >= 0) res[i] = q.peekFirst();
            }
            return res;
        }
    }
}